class Array:
    '''
        数组 Array
    '''
    def __init__(self, arr=None, capacity=10):
        if isinstance(arr, list):  #列表转数组
            self.data = arr[:]
            self.size = len(arr)
        else:
            self.size = 0 #空数组
            self.data = [None] * capacity #默认容量

    def __getitem__(self, index):
        return self.get(index)
    def __setitem__(self, key, value):
        self.set(key, value)
    def __len__(self): #长度不等于容量
        return self.size
    def __contains__(self, value):
        return self.contains(value)
    def __delitem__(self, index):
        self.pop(index)
    def __str__(self):
        return str(f'Array:{self.data[:self.size]}, capacity:{self.get_capacity()}')
    def __repr__(self):
        return self.__str__()

    def get(self, index):
        '''
            获取索引为index的值
        '''
        if index < 0 or index >= self.size:
            raise IndexError("get failed, Required index >= 0 and index <= size")
        return self.data[index]

    def set(self, index, value):
        '''
            将索引为index的值改为value
        '''
        if index < 0 or index >= self.size:
            raise IndexError("set failed, Required index >= 0 and index <= size")
        self.data[index] = value

    def get_capacity(self):
        '''
            获取数组的容量
        '''
        return len(self.data)

    def is_empty(self):
        '''
            判断数组是否为空
        '''
        return self.size == 0

    def insert(self, index, value):
        '''
            在索引为index的位置插入元素value
        '''
        if index < 0 or index > self.size:
            raise IndexError("Add failed, Required index >= 0 and index <= size")

        # 如果数组full，那么扩容一倍
        if self.size == len(self.data):
            if self.size == 0:
                self._resize(1)
            else:
                self._resize(len(self.data) * 2)

        # index之后的元素往后移一位
        for i in range(self.size - 1, index - 1, -1):
            self.data[i + 1] = self.data[i]

        self.data[index] = value
        self.size += 1

    def add(self, value):
        self.insert(self.size, value)

    def _resize(self, new_capacity): 
        '''
            将数组空间的容量变成new_capacity的大小
        '''
        newdata = [None] * new_capacity
        for i in range(self.size):
            newdata[i] = self.data[i]
        self.data = newdata

    def contains(self, value):
        '''
            查看数组中是否包含元素value，包含则返回True，否则返回False
        '''
        for i in range(self.size):
            if self.data[i] == value:
                return True
        return False

    def index(self, value):
        '''
            查找元素值为value在数组中的索引，如果不存在，则返回-1
        '''
        for i in range(self.size):
            if self.data[i] == value:
                return i
        return -1

    def remove(self, value):
        '''
            删除数组中值为value的元素
        '''
        index = self.index(value)
        self.pop(index)

    def pop(self, index=None):
        '''
            从数组中删除索引为index的元素，并返回删除的元素值
        '''
        if index==None : index = self.size-1
        if index < 0 or index >= self.size:
            raise IndexError("remove failed, Required index >= 0 and index < size")

        ret = self.data[index]

        # index之后的元素往前移动一位
        for i in range(index + 1, self.size):
            self.data[i - 1] = self.data[i]
        self.size -= 1

        # 如果数组元素小于容量的1/4，则缩小容量至原有的1/2
        if self.size < len(self.data) // 4 and len(self.data) // 2 != 0:
            self._resize(len(self.data) // 2)
        return ret

    def swap(self, i, j):
        '''
            交换索引为i和j两个位置的值
        '''
        if i < 0 or i >= self.size or j < 0 or j >= self.size:
            raise IndexError("index is illegal")
        self.data[i], self.data[j] = self.data[j], self.data[i]


if __name__ == "__main__":

    array = Array([i for i in range(10)])
    print(array)

    array.add(10)
    print(array)

    array.insert(0, -1)
    print(array.index(-1))
    print(array[0])

    array[1]=99
    array.pop()
    array.pop(0)
    array.remove(3)
    array.swap(5,6)
    print(array)

    print(3 in array)
